package digui;

public class _08第K个元素 {
    //以尽量高的效率求出一个乱序数组中按数值顺序的第K个元素
    public static void main(String[] args) {
        int[] a ={3,9,7,6,1,2};
        int k =selectK(a,0,a.length-1,6);
        System.out.println(k);
    }

    //利用快排，求出主元，如果主元的下标正好是目标位置，直接返回
    //主元下标大于目标位置，左边寻找，反之右边寻找
    public static int selectK(int[] a,int p,int r,int k){
        int q = partition(a,p,r);
        int qk = q-p+1;//主元的位置
        if (k == qk){
            return a[q];
        }else if (k < qk){
            return selectK(a,p,q-1,k);
        }else {
            return selectK(a,q+1,r,k-qk);//在主元右边寻找时，需要注意此时将右边数组视为新数组，目标位置发生改变
        }
    }

    //单向指针扫描快速排序确定分界点（左边元素小于分界，右边元素大于分界）
    public static int partition(int [] a,int p,int r){
        int pivot = a[p];  //主元
        int sp = p+1;  //扫描指针
        int bigger = r;//右侧指针
        while (sp <= bigger){
            if (a[sp] <= pivot){   //扫描元素小于主元，左指针向右移
                sp ++;
            }else { //扫描元素大于主元，二指针元素交换，右指针左移
                swap(a,sp,bigger);
                bigger--;
            }
        }
        swap(a,p,bigger);  //交换主元和右指针位置，此时主元位置就是分界点
        return bigger;
    }

    private static void swap(int[] a, int pivot, int i) {
        int temp = a[pivot];
        a[pivot] = a[i];
        a[i]= temp;
    }
}
